package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author feizns
 * @since 2020/1/6
 */
public class LeafSimilar {

    public static void main(String[] args) {
        System.out.println(leafSimilar(create1(), create2()));
    }

    public static TreeNode create1() {
        TreeNode ret = new TreeNode(18);
        ret.left = new TreeNode(35);
        ret.right = new TreeNode(22);
        ret.left.right = new TreeNode(103);
        ret.left.right.left = new TreeNode(58);
        ret.right.left = new TreeNode(43);
        ret.right.right = new TreeNode(101);
        ret.left = new TreeNode(97);
        return ret;
    }

    public static TreeNode create2() {
        TreeNode ret = new TreeNode(94);
        ret.left = new TreeNode(102);
        ret.left.left = new TreeNode(122);
        ret.left.left.left = new TreeNode(58);
        ret.left.left.right = new TreeNode(101);
        ret.right = new TreeNode(17);
        ret.right.right = new TreeNode(54);
        ret.right.right.left = new TreeNode(97);
        return ret;
    }

    public static boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Queue<Integer> val = collectLeafVal(root1, new LinkedList<>());
        return consumerQueue(root2, val) && val.isEmpty();
    }

    private static boolean consumerQueue(TreeNode node, Queue<Integer> val) {
        if ( node != null ) {
            if ( consumerQueue(node.left, val) ) {
                if ( isLeaf(node) && (val.isEmpty() || !val.poll().equals(node.val)) )
                    return false;
            } else
                return false;
            return consumerQueue(node.right, val);
        }
        return true;
    }

    private static Queue<Integer> collectLeafVal(TreeNode root, Queue<Integer> queue) {
        if ( root != null ) {
            collectLeafVal(root.left, queue);
            if ( isLeaf(root) )
                queue.add(root.val);
            collectLeafVal(root.right, queue);
        }
        return queue;
    }

    private static boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }

}
